package Sort.sort;

//�鲢����,�ݹ�ʵ�֣��ȶ�����
public class MergeSort {

	public static void main(String[] args) {
		int[] array={9,1,5,8,3,7,4,6,2};
		mergeSort(array);
		for(int i=0;i<array.length;i++){
			System.out.print(array[i]);
		}
	}
	public static void mergeSort(int[] array){
		if(array==null||array.length==0){
			return;
		}
		sort(array,0,array.length-1);
	}
	public static void sort(int[] array,int start,int end){
		if(start==end){
			return;
		}
		int mid=(start+end)/2;
		sort(array, start, mid);
		sort(array, mid+1, end);
		merge(array,start,mid,end);
	}
	public static void merge(int[] array,int start,int mid,int end){
		int[] tempArr=new int[end-start+1];
		int left =start;
		int right = mid+1;
		int third = 0;
		while(left<=mid&&right<=end){
			if(array[left]<array[right]){
				tempArr[third++]=array[left++];
			}
			else{
				tempArr[third++]=array[right++];
			}
		}
		while(left<=mid){
			tempArr[third++]=array[left++];
		}
		while(right<=end){
			tempArr[third++]=array[right++];
		}
		int i=0;
		while(start<=end){
			array[start++]=tempArr[i++];
		}
		
	}

}
